package leetcode_jz_offer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 美女
 * @date 2022/08/16 14:12
 **/
public class Num37_序列与反序列化二叉树 {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {//二叉树-》字符串：借用队列（层序遍历保证顺序），二叉树元素入队，判断时用rea.append拿到二叉树数字内容
        if(root==null){
            return "[]";
        }
        StringBuilder res=new StringBuilder("[");
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        //二叉树中元素依次出队入队判断，元素不为空res+元素值，为空res+null
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                res.append(cur.val+",");
                queue.add(cur.left);
                queue.add(cur.right);
            }else{
                res.append("null,");
            }
        }
        res.deleteCharAt(res.length()-1);
        res.append("]");
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {//字符串-》二叉树
        if(data.equals("[]")){
            return null;
        }
        String[] str = data.substring(1, data.length() - 1).split(",");
        TreeNode root=new TreeNode(Integer.parseInt(str[0]));

        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int i=1;//通过i遍历，遇到null跳过.i从1开始，因为root已经处理过了
        while (!queue.isEmpty()){
            //出队当前元素判断队列内当前元素值是否为null,不是null就要创建左右节点
            TreeNode cur=queue.poll();
            if(!str[i].equals("null")){
                cur.left=new TreeNode(Integer.parseInt(str[i]));
                queue.add(cur.left);
            }
            i++;
            if(!str[i].equals("null")){
                cur.right=new TreeNode(Integer.parseInt(str[i]));
                queue.add(cur.right);
            }
            i++;
        }
        return root;
    }
    private class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
